/*
 * @lc app=leetcode.cn id=93 lang=typescript
 *
 * [93] 复原 IP 地址
 */

// @lc code=start
function restoreIpAddresses(s: string): string[] {
  const arr = s.split('');
  const ans = [];
  const backtrack = (k: number, idx: number) => {
    if (idx >= arr.length) return;
    // 3个点都插入完成了
    if (k === 4) {
      // 最后一组数字是否是0开头
      if (arr.length - idx > 1 && arr[idx] === '0') return;
      let num = 0;
      // 最后一组数字是否大于255
      for (let i = idx; i < arr.length; i++) {
        num = num * 10 + Number(arr[i]);
        if (num > 255) return;
      }
      // 更新答案
      ans.push(arr.join(''));
    }
    let num = 0;
    for (let i = idx; i < arr.length; i++) {
      num = num * 10 + Number(arr[i]);
      // 数字大于255，结束
      if (num > 255) return;
      // 数字第一位大于0，结束
      if (i - idx >= 1 && arr[idx] === '0') return;
      // 选择插入点
      arr.splice(i + 1, 0, '.');
      // 递归下一个点的位置
      backtrack(k + 1, i + 2);
      // 回溯，删除插入的点
      arr.splice(i + 1, 1);
    }
  };

  backtrack(1, 0);

  return ans;
}
// @lc code=end
